By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 28, Issue 4, pp. 1155-1539

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine

Hans Kellerer, T. Tautenhahn, and G. Woeginger

pp. 1155-1166

BibTeX  Abstract Full Text:  PDF

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani

pp. 1167-1181

BibTeX  Abstract Full Text:  PDF

Constructing Approximate Shortest Path Maps in Three Dimensions

Sariel Har-Peled

pp. 1182-1197

BibTeX  Abstract Full Text:  PDF

New Lower Bounds for Convex Hull Problems in Odd Dimensions

Jeff Erickson

pp. 1198-1214

BibTeX  Abstract Full Text:  PDF

The Height and Size of Random Hash Trees and Random Pebbled Hash Trees

Luc Devroye

pp. 1215-1224

BibTeX  Abstract Full Text:  PDF

On Rearrangeability of Multirate Clos Networks

Guo-Hui Lin, Ding-Zhu Du, Xiao-Dong Hu, and Guoliang Xue

pp. 1225-1231

BibTeX  Abstract Full Text:  PDF

Design of On-Line Algorithms Using Hitting Times

Prasad Tetali

pp. 1232-1246

BibTeX  Abstract Full Text:  PDF

Efficient Generation of Minimal Length Addition Chains

Edward G. Thurber

pp. 1247-1263

BibTeX  Abstract Full Text:  PDF

Distributional Word Problem for Groups

Jie Wang

pp. 1264-1283

BibTeX  Abstract Full Text:  PDF

Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs

Derek G. Corneil, Stephan Olariu, and Lorna Stewart

pp. 1284-1297

BibTeX  Abstract Full Text:  PDF

Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems

Joseph S. B. Mitchell

pp. 1298-1309

BibTeX  Abstract Full Text:  PDF

Fine Separation of Average-Time Complexity Classes

Jin-Yi Cai and Alan L. Selman

pp. 1310-1325

BibTeX  Abstract Full Text:  PDF

Buckets, Heaps, Lists, and Monotone Priority Queues

Boris V. Cherkassky, Andrew V. Goldberg, and Craig Silverstein

pp. 1326-1346

BibTeX  Abstract Full Text:  PDF

Distributed Anonymous Mobile Robots: Formation of Geometric Patterns

Ichiro Suzuki and Masafumi Yamashita

pp. 1347-1363

BibTeX  Abstract Full Text:  PDF

A Pseudorandom Generator from any One-way Function

Johan HÅstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby

pp. 1364-1396

BibTeX  Abstract Full Text:  PDF

Local Labeling and Resource Allocation Using Preprocessing

Hagit Attiya, Hadas Shachnai, and Tami Tamir

pp. 1397-1414

BibTeX  Abstract Full Text:  PDF

Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method

Harry Buhrman, Jaap-Henk Hoepman, and Paul Vitányi

pp. 1414-1432

BibTeX  Abstract Full Text:  PDF

Computing with Very Weak Random Sources

Aravind Srinivasan and David Zuckerman

pp. 1433-1459

BibTeX  Abstract Full Text:  PDF

Lower Bounds in a Parallel Model without Bit Operations

Ketan Mulmuley

pp. 1460-1509

BibTeX  Abstract Full Text:  PDF

Stack and Queue Layouts of Directed Acyclic Graphs: Part I

Lenwood S. Heath, Sriram V. Pemmaraju, and Ann N. Trenk

pp. 1510-1539

BibTeX  Abstract Full Text:  PDF